﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class Trees
    {
        public Trees()
        {
            int testCount = Int32.Parse(Console.ReadLine());
            for (int testCase = 1; testCase <= testCount; testCase++)
            {
                string[] input = Console.ReadLine().Split(' ');
                int treeCount = Int32.Parse(input[0]);
                int pollCount = Int32.Parse(input[1]);
                int need = Int32.Parse(input[2]);
                //Console.WriteLine();
                //Console.WriteLine(treeCount + " " + need);
                int[] powerMap = new int[20000];
                powerMap[0] = int.MaxValue;
                int[] powerList = new int[pollCount];
                int[,] powerBoard = new int[pollCount, pollCount + 1];
                for (int i = 0; i < pollCount; i++)
                {
                    input = Console.ReadLine().Split(' ');
                    int power = Int32.Parse(input[0]);
                    int count = Int32.Parse(input[1]);
                    powerMap[power] = count;
                    powerList[i] = power;
                }
                List<int[]> sufficient = new List<int[]>();
                for (int y = 0; y < pollCount; y++)
                {
                    for (int x = 0; x < pollCount + 1; x++)
                    {
                        if (x == 0 && powerMap[powerList[y]] > 0)
                        {
                            powerBoard[y, x] = powerList[y];
                            sufficient.Add(new int[3] { powerList[y], -1, y });
                        }
                        else if (x > 0 && (powerList[x - 1] == powerList[y]) && powerMap[powerList[y]] > 1)
                        {
                            powerBoard[y, x] = powerList[x - 1] + powerList[y];
                            sufficient.Add(new int[3] { powerList[x - 1] + powerList[y], x - 1, y });
                        }
                        else if (x > 0 && (powerList[x - 1] != powerList[y]) && powerMap[powerList[y]] > 0)
                        {
                            powerBoard[y, x] = powerList[x - 1] + powerList[y];
                            sufficient.Add(new int[3] { powerList[x - 1] + powerList[y], x - 1, y });
                        }
                    }
                }
                List<int[]> orderList = sufficient.OrderBy(s => s[0]).ToList<int[]>();
                int sum = 0;
                int restCount = treeCount;
                for (int i = 0; i < orderList.Count(); i++)
                {
                    if (orderList[i][0] >= need)
                    {
                        int aPower = (orderList[i][1] > -1) ? powerList[orderList[i][1]] : 0;
                        int bPower = powerList[orderList[i][2]];
                        int count = Math.Min(powerMap[aPower], powerMap[bPower]);
                        if (orderList[i][1] == orderList[i][2])
                        {
                            count /= 2;
                        }
                        if (count < restCount)
                        {
                            restCount -= count;
                            powerMap[aPower] -= count;
                            powerMap[bPower] -= count;
                            sum += count * orderList[i][0];
                            if (count > 0)
                            {
                                //Console.WriteLine(aPower + " " + bPower + " " + count);
                            }
                        }
                        else
                        {
                            count = restCount;
                            if (orderList[i][0] * count < need * restCount)
                            {
                                count++;
                            }
                            restCount -= (count);
                            powerMap[aPower] -= (count);
                            powerMap[bPower] -= (count);
                            sum += (count) * orderList[i][0];
                            if (count > 0)
                            {
                                //Console.WriteLine(aPower + " " + bPower + " " + count);
                            }
                            break;
                        }
                    }
                }
                if (sum >= need * treeCount)
                {
                    //Console.WriteLine("Case #" + testCase + ": " + treeCount + " " + need + " " + sum);
                    Console.WriteLine("Case #" + testCase + ": " + sum);
                }
                else
                {
                    Console.WriteLine("Case #" + testCase + ": -1");
                }
            }
        }
    }
}
